import tool.TreeNode;
import tool.TreeNodePrint;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description: 最大二叉树
 * 给定一个不重复的整数数组 nums 。 
 * 最大二叉树 可以用下面的算法从 nums 递归地构建:
 * 创建一个根节点，其值为 nums 中的最大值。
 * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 返回 nums 构建的 最大二叉树 。
 * @Date:Create in 17:53  2022/8/2
 */
public class constructMaximumBinaryTree0654 {

    Map<Integer, Integer> map;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int len = nums.length;
        if (len == 0) return null;
        map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(nums[i], i);
        }
        return findNode(nums,0,len-1);
    }

    public TreeNode findNode(int[] nums, int begin, int end) {
        if (end - begin < 0) return null;
        int max = maxVal(begin, end, nums);
        int index = map.get(max);
        TreeNode root = new TreeNode(max);
        root.left = findNode(nums,begin,index-1);
        root.right = findNode(nums,index+1,end);
        return root;
    }

    public static int maxVal(int begin, int end, int[] nums) {
        int temp = 0;
        for (; begin <= end; begin++) {
            if (nums[begin] >= temp) {
                temp = nums[begin];
            }
        }
        return temp;
    }
}

class Main{
    public static void main(String[] args) {
        constructMaximumBinaryTree0654 con = new constructMaximumBinaryTree0654();
        int[] nums = {3,2,1,6,0,5};
        TreeNode root = con.constructMaximumBinaryTree(nums);
        TreeNodePrint.printTree(root);
    }
}
